package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-10 00:05
 **/
public class LeetCode306 {

    public static void main(String[] args) {
        LeetCode306 code = new LeetCode306();
        code.isAdditiveNumber("112358");
    }

    public boolean isAdditiveNumber(String num) {
        int n = num.length();
        //只要确定了第二个数,第一个数就确定了,然后循环判断后面的数
        for (int secondStart = 1; secondStart < 2 * n / 3; ++secondStart) {
            for (int secondEnd = secondStart; secondEnd < 2 * n / 3; ++secondEnd) {
                //当某个数字长度大于等于 2 时，这个数字不能以 0 开头
                if (num.charAt(secondStart) == '0' && secondStart != secondEnd) {
                    break;
                }
                //判断第二个数为[secondStart, secondEnd]组成的数字字符串,是否可以形成累加序列
                if (valid(secondStart, secondEnd, num)) {
                    return true;
                }
            }
        }
        return false;
    }


    /**
     * 判断第二个数为[secondStart,secondEnd]组成的数字字符串是否为合法的累加序列
     * @param secondStart
     * @param secondEnd
     * @param num
     * @return
     */
    public boolean valid(int secondStart, int secondEnd, String num) {
        int n = num.length();
        int firstStart = 0;
        int firstEnd = secondStart - 1;
        while (secondEnd <= n - 1) {
            //计算前两个数相加的结果字符串
            String third = stringAdd(num, firstStart, firstEnd, secondStart, secondEnd);
            //计算第三个数的开头索引
            int thirdStart = secondEnd + 1;
            //计算第三个数的结尾索引
            int thirdEnd = secondEnd + third.length();
            //如果第三个数越界了或者累加数不匹配,则失败直接终止循环,退出返回false
            if (thirdEnd >= n || !num.substring(thirdStart, thirdEnd + 1).equals(third)) {
                break;
            }
            //如果第三个数的结尾刚好到了字符串的末尾,说明找到了累加数序列,返回true
            if (thirdEnd == n - 1) {
                return true;
            }
            //更新第一个数的开头
            firstStart = secondStart;
            //更新第一个数的结尾
            firstEnd = secondEnd;
            //更新第二个数的开头
            secondStart = thirdStart;
            //更新第二个数的结尾
            secondEnd = thirdEnd;
        }
        return false;
    }

    /**
     * 计算两个两个字符串表示的数字从低位到高位相加得到数字结果再转成字符串
     * @param s
     * @param firstStart
     * @param firstEnd
     * @param secondStart
     * @param secondEnd
     * @return
     */
    public String stringAdd(String s, int firstStart, int firstEnd, int secondStart, int secondEnd) {
        StringBuilder third = new StringBuilder();
        int carry = 0;
        int cur = 0;
        while (firstEnd >= firstStart || secondEnd >= secondStart || carry != 0) {
            //将从低位的进位赋值给当前位的初始值
            cur = carry;
            if (firstEnd >= firstStart) {
                cur += s.charAt(firstEnd) - '0';
                --firstEnd;
            }
            if (secondEnd >= secondStart) {
                cur += s.charAt(secondEnd) - '0';
                --secondEnd;
            }
            //计算进位
            carry = cur / 10;
            //计算当前位的值
            cur %= 10;
            //将整形数转成字符添加到StringBuilder,此时是按个位,十位,百位的顺序添加的,
            third.append((char) (cur + '0'));
        }
        //将字符串颠倒得到正确的顺序
        third.reverse();
        //返回两个数字字符串相加的结果字符串
        return third.toString();
    }

}
